/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/n-queens
   @Language: C++
   @Datetime: 19-06-20 10:17
   */

class Solution {
	bool isValid(vector<string> &v, int row, int col){
		bool valid=true;
		for(int i=0; valid && i<row; valid=v[i++][col]!='Q');
		for(int i=0; valid && i<col; valid=v[row][i++]!='Q');
		for(int i=row, j=col; valid && i-- && j--; valid=v[i][j]!='Q');
		for(int i=row, j=col; valid && i-- && ++j<v.size(); valid=v[i][j]!='Q');
		return valid;
	}
	void backtrack(vector<string> &v, int row, vector<vector<string> > &vs){
		if(row==v.size()){
			vs.push_back(v);
			return;
		}
		for(int col=0; col<v.size(); ++col){
			v[row][col]='Q';
			if(isValid(v,row,col)) backtrack(v,row+1,vs);
			v[row][col]='.';
		}
	}
public:
	vector<vector<string> > solveNQueens(int n) {
		vector<string> v(n,string(n,'.'));
		vector<vector<string> > vs;
		backtrack(v,0,vs);
		return vs;
	}
};
